19E - Fairy - CodeForces Solution

//sim 1 - E
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, m;
vector<pair<int*, int>> ch;

void rollback(){
	pair<int*, int> cr = ch.back();
	ch.PPB();
	*cr.X = cr.Y;
}

struct union_find{
	int par[MAXN], sz[MAXN], ds[MAXN];
	
	void init(){
		for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1, ds[i] = 0;
	}
	
	int find(int x){
		return x == par[x] ? x : find(par[x]);
	}
	
	int dis(int x){
		int d = 0;
		while(x != par[x]) d ^= ds[x], x = par[x];
		return d;
	}
	
	bool unite(int a, int b){
		int da = dis(a), db = dis(b);
		a = find(a), b = find(b);
		if(a == b) return da != db;
		if(sz[a] < sz[b]) swap(a, b);
		
		ch.PB({&sz[a], sz[a]});
		sz[a] += sz[b];
		
		ch.PB({&par[b], par[b]});
		par[b] = a;
		
		ch.PB({&ds[b], ds[b]});
		ds[b] = (1 ^ da ^ db);
		return 1;
	}
}uf;

vi ret;



struct dynacon{
	vii seg[trsz];
	
	void update(int l, int r, ii vl){
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) seg[l].PB(vl), l++;
			if(r & 1) --r, seg[r].PB(vl);
		}
	}
	
	void dfs(int x, bool gd){
		int psz = ch.size();
		for(auto &y : seg[x]) gd &= uf.unite(y.X, y.Y);
		
		if(x >= off){
			if(x - off < m and gd) ret.PB(x - off + 1);
		}else{
			if(gd){
				dfs(x * 2, gd);
				dfs(x * 2 + 1, gd);
			}
		}
		
		while((int)ch.size() != psz) rollback();
	}
}t;

void solve(){
	cin >> n >> m;
	uf.init();
	for(int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		if(i) t.update(0, i, {a, b});
		if(i != m - 1) t.update(i + 1, m, {a, b});
	}
	
	t.dfs(1, 1);
	
	cout << ret.size() << "\n";
	for(auto &x : ret) cout << x << " ";
	cout << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}